package leetcode_bin_tree_test;

import bin_tree.TreeNode;

import java.util.*;

/**
 * 二叉树的所有路径
 */
public class BinaryTreePaths {
    List<String> ret = new ArrayList<>();
    public static List<String> binaryTreePaths(TreeNode root) {
        // 深度优先遍历
//        if (root == null) {
//            return ret;
//        }
//        findPath(root, new String());
//        return ret;

        // 广度优先遍历
        // 特别注意String（传值）和StringBuilder（共用同一个StringBuilder对象）的区别
        List<String> paths = new ArrayList<>();
        if (root == null) {
            return paths;
        }
        Deque<TreeNode> nodeQueue = new ArrayDeque<>();
        Deque<String> pathQueue = new ArrayDeque<>();
        nodeQueue.offer(root);
        pathQueue.offer(String.valueOf(root.val));
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            String path = pathQueue.poll();
            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQueue.offer(new StringBuilder(path).append("->").append(node.left.val).toString());
                }
                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQueue.offer(new StringBuilder(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return paths;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        binaryTreePaths(root);
    }

    // StringBuilder有不可变性，不能用
    public void findPath(TreeNode root, String path) {
        if (root.left == null && root.right == null) {
            // 到达了叶子节点
            path += root.val;
            ret.add(path);
            return;
        }
        path += root.val + "->";
        if (root.left != null) {
            findPath(root.left, path);
        }
        if (root.right != null) {
            findPath(root.right, path);
        }
    }
}
